#!/usr/bin/python2.4
#
# Copyright 2010 Google Inc.

# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0

# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

import random

BASE = 32

class BitArray(object):
  # TODO(robni): Make this into immutable objects to get haching right
  def __init__(self, l):
    self.length = l
    self.data = [0] * ((l / BASE) + 1)

  def Copy(self, other):
    self.data = other.data[:]
    self.lenght = other.length

  def Randomize(self):
    for i in self.data:
      i = random.getrandbits(BASE)

  def _CrossWord(self, word_offset, other):
    if word_offset > len(self.data):
      return
    for i in xrange(word_offset, len(self.data)):
      tmp = self.data[i]
      self.data[i] = other.data[i]
      other.data[i] = tmp

  def Cross(self, ind, other):
    word_offset = ind / BASE
    bit_offset = ind % BASE
    if not bit_offset:
      self._CrossWord(word_offset, other)
      return
    else:
      self._CrossWord(word_offset + 1, other)
      self.data[word_offset], other.data[word_offset] = self._CrossBits(
          bit_offset,  self.data[word_offset], other.data[word_offset])

  def _CrossBits(self, offset, first, second):
    return (CopyBits(second, offset), CopyBits(first, offset))

  def __repr__(self):
    return 'ByteArray(%d):%s' % (self.length, self.__str__())

  def __str__(self):
    s = ''
    for i in xrange(0, self.length):
      if self.IsSet(i):
        s += '1'
      else:
        s += '0'
    return s

  def __eq__(self, other):
    return self.data == other.data

  def __ne__(self, other):
    return not self.data == other.data

  def __getitem__(self, index):
    return self.IsSet(index)

  def __setitem__(self, index, value):
    self.Set(index, value)

  def IsSet(self, ind):
    word_offset = ind / BASE
    if ind >= self.length:
      raise Exception

    bit_offset = ind % BASE
    and_mask = pow(2, bit_offset)
    return (self.data[word_offset] & and_mask) == and_mask

  def Set(self, ind, value):
    word_offset = ind / BASE
    if ind >= self.length:
      raise Exception
    bit_offset = ind % BASE
    if value:
      self.data[word_offset] = SetBit(self.data[word_offset],
                                      bit_offset)
    else:
      self.data[word_offset] = ClearBit(self.data[word_offset],
                                        bit_offset)


def SetBit(word, offset):
  mask = 1 << offset
  return word | mask

def ClearBit(word, offset):
  mask = ~(1 << offset)
  return word & mask

def CopyBits(word, offset):
  new_word = 0
  for i in xrange(offset, BASE):
    if BitIsSet(word, i):
      new_word = SetBit(new_word, i)
    else:
      new_word = ClearBit(new_word, i)
  return new_word

def BitIsSet(word, ind):
  and_mask = pow(2, ind)
  return (word & and_mask) == and_mask
